function permute(arr) {
  var rs = [];
  // 递归
  // 1234
  // 1 - 234的全排列
  // 2 - 134的全排列
  // 3 - 124的全排列
  // 4 - 123的全排列
  // 跳出条件
  if (arr.length === 2) {
    rs.push([...arr]);
    rs.push([arr[1], arr[0]]);
  }
  for (var i = 0; i < arr.length; i++) {
    var _arr = [...arr];
    var temp = _arr.splice(i, 1);
    // rs.push()
    permute(_arr).forEach((item) => {
      rs.push(temp.concat(item));
    });
  }
  return rs;
}
console.log(permute([1, 2, 3, 4]));

// 回溯框架解决
function per(nums) {
  var res = [];
  var track = []; //路径列表
  sel(nums, track);
  return res;

  function sel(nums, track) {
    if (track.length == nums.length) {
      res.push(track);
      return;
    }
    for (var i = 0; i < nums.length; i++) {
      if (track.includes(nums[i])) {
        continue;
      }
      // 做选择
      track.push(nums[i]);
      sel(nums, track);
      // 撤销选择
      track.pop();
    }
  }
}
console.log(per([1, 2, 3, 4]));
